﻿#pragma once

#include <iostream>
#include <string>
using namespace std;


//⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:
//• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
//• 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
//• 它的左右⼦树也分别为⼆叉搜索树
//• ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后续我
//们学习map / set / multimap / multiset系列容器底层就是⼆叉搜索树，其中map / set不⽀持插⼊相等
//值，multimap / multiset⽀持插⼊相等值


//只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断
//key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查，但是不⽀持修改，修改key破坏搜索树结
//构了。
//set雏形
namespace key
{
	template <class K>
	struct BSTNode
	{

		BSTNode(const K& key)
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{

		}

		K _key;
		BSTNode<K>* _left;
		BSTNode<K>* _right;
	};

	template <class K>
	class BSTree
	{
	public:

		typedef BSTNode<K> Node;



		//插⼊的具体过程如下：
		/*1. 树为空，则直接新增结点，赋值给root指针
			2. 树不空，按⼆叉搜索树性质，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到空位
			置，插⼊新结点。
			3. 如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插
			⼊新结点。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右⾛，⼀会往左⾛）*/
		bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
			}

			Node* cur = _root;
			Node* parent = nullptr;


			while (cur)
			{
				if (cur->_key < key)//if (cur->_key <= key) 若有相等的值，统一向一边走
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key);
			if (parent->_key < key)//if (parent->_key <= key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;


		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}


		/*⼆叉搜索树的删除
			⾸先查找元素是否在⼆叉搜索树中，如果不存在，则返回false。
			如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）
			1. 要删除结点N左右孩⼦均为空
			2. 要删除的结点N左孩⼦位空，右孩⼦结点不为空
			3. 要删除的结点N右孩⼦位空，左孩⼦结点不为空
			4. 要删除的结点N左右孩⼦结点均不为空

			对应以上四种情况的解决⽅案：
			1. 把N结点的⽗亲对应孩⼦指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样
			的）
			2. 把N结点的⽗亲对应孩⼦指针指向N的右孩⼦，直接删除N结点
			3. 把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，直接删除N结点
			4. ⽆法直接删除N结点，因为N的两个孩⼦⽆处安放，只能⽤替换法删除。找N左⼦树的值最⼤结点
			R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的
			位置，都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转⽽变成删除R结
			点，R结点符合情况2或情况3，可以直接删除。*/
		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					// 0-1个孩⼦的情况
                    // 删除情况1 2 3均可以直接删除，改变⽗亲对应孩⼦指针指向即可
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}

						}

						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
						return true;
					}
					else
					{
						// 2个孩⼦的情况
                        // 删除情况4，替换法删除
                        // 假设这⾥我们取右⼦树的最⼩结点(最左结点）作为替代结点去删除
                        // 这⾥尤其要注意右⼦树的根就是最⼩情况的情况的处理，对应课件图中删
						//除8的情况，⼀定要把cur给replaceParent，否会报错。
						Node* replaceParent = cur;//这里等于nullptr不行，当replace就是最左节点时，没有进循环，而replaceParent就还等于nullptr，访问左右节点时会报错
						Node* replace = cur->_right;

						while (replace->_left)
						{
							replaceParent = replace;
							replace = replace->_left;
						}

						cur->_key = replace->_key;

						if (replaceParent->_left == replace)
						{
							replaceParent->_left = replace->_right;
						}
						else if (replaceParent->_right == replace)
						{
							replaceParent->_right = replace->_right;
						}

						delete replace;
						return true;
					}
				}
			}

			return false;
		}


		bool Find(const K& key)
		{
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return true;
				}
			}
			return false;
		}

	private:

		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}

		Node* _root = nullptr;
	};
}


//每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存
//储key还要存储对应的value，增 / 删 / 查还是以key为关键字⾛⼆叉搜索树的规则进⾏⽐较，可以快速查
//比特就业课
//找到key对应的value。key / value的搜索场景实现的⼆叉树搜索树⽀持修改，但是不⽀持修改key，修
//改key破坏搜索树性质了，可以修改value。
//map雏形
namespace key_value
{
	template <class K,class V>
	struct BSTNode
	{

		BSTNode(const K& key,const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{

		}

		K _key;
		V _value;
		BSTNode<K,V>* _left;
		BSTNode<K,V>* _right;
	};

	template <class K,class V>
	class BSTree
	{
	public:

		typedef BSTNode<K,V> Node;

		BSTree() = default;

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

		BSTree(const BSTree<K,V>& bst)
		{
			_root = Copy(bst._root);
		}

		BSTree<K,V>& operator=(BSTree<K,V> bst)
		{
			swap(_root, bst._root);
			return *this;
		}

		bool Insert(const K& key,const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key,value);
			}

			Node* cur = _root;
			Node* parent = nullptr;


			while (cur)
			{
				if (cur->_key < key)//if (cur->_key <= key) 若有相等的值，统一向一边走
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key,value);
			if (parent->_key < key)//if (parent->_key <= key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;


		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}

						}

						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
						return true;
					}
					else
					{
						Node* replaceParent = cur;
						Node* replace = cur->_right;

						while (replace->_left)
						{
							replaceParent = replace;
							replace = replace->_left;
						}

						cur->_key = replace->_key;

						if (replaceParent->_left == replace)
						{
							replaceParent->_left = replace->_right;
						}
						else if (replaceParent->_right == replace)
						{
							replaceParent->_right = replace->_right;
						}

						delete replace;
						return true;
					}
				}
			}

			return false;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}

	private:

		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			_InOrder(root->_left);
			cout << root->_key << "," << root->_value << endl;
			_InOrder(root->_right);
		}

		//销毁采用后序遍历，先左右子树，后根
		void Destroy(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		//拷贝采用前序遍历，先根，后左右子树
		Node* Copy(Node* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}

			Node* newnode = new Node(root->_key, root->_value);
			newnode->_left=Copy(root->_left);
			newnode->_right=Copy(root->_right);

			return newnode;
		}

		Node* _root = nullptr;
	};
}

